package 学习计划.数据结构;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author 会玩的洋洋
 * https://leetcode.cn/problems/non-overlapping-intervals/?envType=study-plan&id=shu-ju-jie-gou-ji-chu&plan=data-structures&plan_progress=cqjfoh6
 */
public class _435_无重叠区间 {
    /**
     * 动态规划
     * 超时，但没问题
     * @param intervals
     * @return
     */
    public int eraseOverlapIntervals(int[][] intervals) {
        int n = intervals.length;
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        int ret = 0;
        int[] f = new int[n];
        Arrays.fill(f, 1);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (intervals[j][1] <= intervals[i][0]) {
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
        }
        return n - Arrays.stream(f).max().getAsInt();
    }

    /**
     * 贪心算法
     * 执行时间：46ms，内存消耗：98.1MB
     * @param intervals
     * @return
     */
    public int eraseOverlapIntervals2(int[][] intervals) {
        int n = intervals.length;
        if (n == 0) {
            return 0;
        }

        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });

        int right = intervals[0][1];
        int ret = 1;
        for (int i = 1; i < n; i++) {
            if (intervals[i][0] >= right) {
                ret++;
                right = intervals[i][1];
            }
        }
        return n - ret;
    }
}
